package main;

import java.util.ArrayDeque;

/**
 *滑动窗口最大值
 * 给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 *
 * 返回滑动窗口中的最大值。
 * @author kejl
 * @version test
 * @date 2020/5/29 9:13
 */
public class ShuangDuanDuiLie {


    public static void main(String[] args) {
        int[] ddd = new int[]{1,3,-1,-3,5,3,6,7};
        new ShuangDuanDuiLie().maxSlidingWindow(ddd,3);
    }


    ArrayDeque<Integer> deq = new ArrayDeque<Integer>();
    int [] nums;

    public void clean_deque(int i, int k) {
        // remove indexes of elements not from sliding window
        if (!deq.isEmpty() && deq.getFirst() == i - k)//这个移除是把你已经取的最大的但是，已经超出了k的范围之外，但是还在队列之中
            deq.removeFirst();

        // remove from deq indexes of all elements
        // which are smaller than current element nums[i]
        while (!deq.isEmpty() && nums[i] > nums[deq.getLast()])// 关键： 1.如果它的后一个元素比之前的大那么就把当前的元素移除，
                                                                            // 让最大的排到最左边，依次这样操作，这样在队列中取的First就是最大的
            deq.removeLast();
    }

    /**
     * 时间复杂度：O(N)，每个元素被处理两次- 其索引被添加到双向队列中和被双向队列删除。
     * 空间复杂度：O(N)，输出数组使用了O(N−k+1) 空间，双向队列使用了 O(k)。
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n * k == 0) return new int[0];
        if (k == 1) return nums;

        // init deque and output
        this.nums = nums;
        int max_idx = 0;
        //如果k范围之内的循环
        for (int i = 0; i < k; i++) {
            clean_deque(i, k);
            deq.addLast(i);
            // compute max in nums[:k]
            if (nums[i] > nums[max_idx]) max_idx = i;
        }
        int [] output = new int[n - k + 1];
        output[0] = nums[max_idx];

        // build output
        for (int i  = k; i < n; i++) {
            clean_deque(i, k);
            deq.addLast(i);
            output[i - k + 1] = nums[deq.getFirst()];//这样我每次取的First的下标元素就是最大的。
        }
        return output;
    }


    /**
     * 暴力破解法
     * 时间复杂度为O(N*k)
     * 空间复杂度：O(N−k+1)，用于输出数组。
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow2(int[] nums, int k) {
        int n = nums.length;
        if (n * k == 0) return new int[0];

        int [] output = new int[n - k + 1];
        for (int i = 0; i < n - k + 1; i++) {
            int max = Integer.MIN_VALUE;
            for(int j = i; j < i + k; j++)
                max = Math.max(max, nums[j]);
            output[i] = max;
        }
        return output;
    }

}
